1. Field of the Invention
The present invention relates to a method and apparatus for generating random permutations and, more particularly, to a technique for producing a random sequence of data elements by permuting an input sequence of blocks of data elements.
2. Description of the Related Art
Numerous techniques exist to generate deterministic random sequences. Random sequences generated from such techniques are useful in a variety of applications, including the formation of hop code sequences in frequency-hopping schemes used in certain communication systems. In frequency-hopping systems, the total available transmission bandwidth is partitioned into a number of sub-bands, and the frequency of the transmitted carrier signal is periodically changed or “hopped” from one sub-band to another. Hopping among frequencies in accordance with a random or pseudo-random sequence substantially avoids interference with other signals transmitted within the same band and makes detection and jamming of transmitted signals difficult for parties other than the intended recipient.
With most conventional frequency-hopping schemes, a random sequence is desired and produced. In a random sequence, the random values produced are equally probable, such that selection of any one of the random values is equally probable for each successive output in the sequence. Thus, with a random sequence, the next frequency hop in the sequence is equally likely to be any one of the frequencies within the transmission bandwidth. However, if each of N random values (or transmission frequencies) is equally probable for each output (hop) in the sequence, one would not expect that, of N successive outputs (hops) in a sequence, each of the N values (frequencies) will occur exactly once.
A random sequence is to be distinguished from a random permutation. With a random permutation, a sequence is produced from a set of values arranged in a random order such that a sequence of N successive outputs includes exactly one occurrence of each of the N values in the set.
The difference between a random sequence and a random permutation can be illustrated with examples involving probabilistic trials. A random sequence can be generated by repeatedly throwing a die and obtaining one of the six possible values (1, 2, 3, 4, 5 and 6). With each trial, there is an equal likelihood of obtaining each of the six possible values. However, if one throws a die six times (or, equivalently, six dice simultaneously), one does not expect each of the possible values to occur exactly once in some random order. By contrast, a random permutation can be produced by placing six numbered tokens in a box and blindly selecting one token at a time until all six token have been selected (or, equivalently, shaking and spilling the tokens and reading their values in order, relative to some predetermined orientation, such as left to right). In the token example, a sequence of six values is produced, where each values occurs exactly once within the sequence.
It may be desirable in certain frequency-hopping schemes to determine the sequence of frequency hops using a random permutation rather than a random sequence. For example, in certain signal transmission and detection schemes, it may be advantageous for each frequency to be used within a given block of time or for the period between reuse of frequencies to be maintained within a predetermined range. Use of a random permutation ensures that, over a relatively short period of time, all of the available frequencies will be used, thereby enhancing the uniformity of frequency use.
Moreover, sequences formed from random permutations may be useful in a variety of other applications. For example, random permutations are used in the encryption technique disclosed in U.S. Pat. No. 5,734,721 to Clark, the disclosure of which is incorporated herein by reference in its entirety. Random permutations are used in the Clark patent to permute blocks of bits. Random permutations also potentially have application in virtually any signal encoding scheme where it is desired to adjust the random encoding in a controlled manner over time, as will become evident.
While effective for permuting bits, the permutation methodology disclosed in the Clark patent requires significant hardware and can become inefficient for certain applications. For example, a permutation useful in a frequency-hopping scheme requires more than simply permuting positions of individual bits. If each available frequency is assigned a number in a sequence, a random hop code sequence of these frequencies can be produced by generating a random permutation of the corresponding numbers. This requires permuting N-bit numbers that represent positions in a sequence rather than permuting individual bits. To illustrate this difference, consider that when binary bits that represent a number are permuted (e.g., the four-bit number 0001), the result is a four bit number formed from these same bit values: 0001, 0010, 0100 or 1000 (respectively representing decimal numbers 1, 2, 4 or 8). In the case of four-bit numbers that represent sixteen transmission frequencies in a frequency-hopping system, the desired process randomly permutes all of the four-bit numbers (0, 1, 2, 3, 4, . . . 14, 15) to obtain, for example: (11, 2, 7, 14, 3, 0, 9, 1, 13, . . . ). Thus, forming a sequence of randomly permuted frequencies requires the capability to permute a block of multi-bit data elements that represent numbers or pieces of information, and not merely the capability to permute individual symbols or bits. A substantial number of random bits and considerable processing would be required to accomplish the task of permuting transmission frequencies in a frequency-hopping scheme using the permutation methodology disclosed in the Clark patent.
Other known techniques for generating random permutations are also relatively inefficient from a hardware or processing standpoint. Furthermore, it would be desirable to have the capability to control the rate at which the permutation is modified, particularly in the frequency-hopping context or other signal encoding schemes.
Accordingly, there remains a need for an efficient and inexpensive implementation of a random permutation methodology that is useful in information transmission schemes that employ frequency-hopping and any other applications requiring a sequence of randomly permuted values.